import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024 —05 —12
 * Time: 20:59
 */
public class TestHeap {
    public int[] elem;
    public int usedsize;
    public TestHeap(){
        this.elem = new int[10]; //初始化给数组elem分配一个大小为10的数组
    }
    public void initiateElem(int[] array){ //initiate是初的意思，初始化
        for(int i = 0 ; i < array.length ; i++){
            elem[i] = array[i];
            usedsize++;
        }
    }

    public void creatHeap(){
        for (int parent = (usedsize-1-1)/2 ; parent >= 0 ; parent--) {   //parent最后一棵树的根节点 （i-1）/2    i = usedsize-1=len-1
            siftDown(parent , usedsize); // 取堆中最大值作为根的方法 usedsize知道了每棵树结束的位置  child > usedsize 就说明这棵树调完了
        }
        System.out.print("大根堆打印：");
        for (int i = 0; i < elem.length; i++) {
            System.out.print(  elem[i]+" ");
        }

    }
    public void siftDown(int parent , int len){
        int child = parent * 2 + 1;  //二叉树下标的结论，记不起来了画图
        while (child < len){
            if (child+1 <len && elem[child] < elem[child+1]){ //第一个条件是确保有右孩子 。第二个确保不越界
                child = child +1; //取孩子节点中最大值的下标
            }
            if(elem[parent] < elem[child]){
                swap(parent,child);
                parent = child ;  //(具体参考下面的swap方法)这两句很关键，比如根节点小于右子树，第一次交换，在比较发现这个根节点比子子树的孩子节点还要小就又要交换
                child = parent* 2 +1;
            }else{    //elem[parent] > elem[child] 父亲节点大于孩子节点，那这个父亲节点肯定也大于他下面的所有节点
                break;
            }
        }

    }


    public void push(int val){
        if (isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);//二倍长度扩容
        }
        //判断满
        elem[usedsize] = val;

        siftup(usedsize);//向上调整，传入的参数是该val的下标，即孩子节点

        usedsize++;

    }
    public boolean isFull(){
        return usedsize == elem.length;
    }
    public void swap(int i , int j){
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp; //交换最大值
    }
    public void siftup(int child){
        int parent = (child -1)/2;
        while (child > 0 ) {  // 因为是指插入一个节点，所以只在一棵树上调整，不用在所有树上调整。
            if (elem[parent] < elem[child]) {
                swap(parent, child);
                child = parent;
                parent =( child -1 ) / 2;
            } else {
                break;
            }
        }
    }

    public int pop(){  // 可以理解为出堆顶元素，（删除元素），打印元素的个数不变但是usedsize在减小
        if (empty()){
            return -1;
        }
        int oldval = elem[0];
        swap(0,usedsize-1);
        usedsize--;
        siftDown(0,usedsize);
        return oldval;
    }

    public boolean empty(){
        return usedsize == 0;
    }


}
